package demo1;

import java.util.*;
//题目3：


















//题目2：用队列来实现栈
class MyStack {
    Queue<Integer> qu1 = new LinkedList<Integer>();
    Queue<Integer> qu2 = new LinkedList<Integer>();

    public MyStack() {

    }

    public void push(int x) {
        //将数据压入有数据的队列中
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }

    }
    public int pop() {
        //执行出栈操作，先判断栈是否为空
        if (empty()) {
            return -1;
        }
        //如果不为空
        if (!qu1.isEmpty()) {
            int len = qu1.size()-1;
            for (int i = 0; i < len; i++) {
                int val = qu1.poll();
                qu2.offer(val);
            }
            //
            return qu1.poll();
        }
        int len = qu2.size() -1 ;
        for (int i = 0; i < len; i++) {
                int val = qu2.poll();
                qu1.offer(val);
            }
        return qu2.poll();
        }
        public int top() {
            // 获取栈顶元素
            //将所有的数据转移到另一个队列中，期间经过一个临时变量，最后临时变量中的值即为栈顶元素
            if(empty()){
                return -1;
            }
            int val = 0;
            if(!qu1.isEmpty()){
               // for(int i=0;i<qu1.size();i++){ //有问题,当qu1执行poll方法后，会出现判断条件发生改变的情况
                while (!qu1.isEmpty()){
                    val = qu1.poll();
                    qu2.offer(val);
                }
            }else{
                while (!qu2.isEmpty()){
                    val = qu2.poll();
                    qu1.offer(val);
                }
            }
            return val;
        }
    public boolean empty() {
        if(qu1.isEmpty()&&qu2.isEmpty()){
            return true;
        }
        return false;
    }
}














//题目 1 循环队列的实现
class MyCircularQueue {
    private  int[] elements;
    public MyCircularQueue(int k) {
        //用数组实现一个循环队列
        this.elements = new int[k];

    }
    //指向首元素的标记
    int first = 0;
    //指向尾元素的标记
    int last = 0 ;
    int size = 0;
    public boolean enQueue(int value) {
        //向循环队列中插入一个元素
        //先判断循环队列是否满
        if(isFull()){
            return false;
        }
        //未满
        this.elements[last] = value;
        last = (last+1)% elements.length;
        size ++;
        return true;
    }
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        //如果队列不为空，返回队尾元素
        //队尾元素的下标不一定为last -1 ,如果last 正好此时为0，那么last-1的结果为-1
        //依旧按照求模的方法求取之前的last之前的元素
        return elements[(last + elements.length-1 )%elements.length];
    }
    public boolean deQueue() {
        //从队列中删除一个元素，删除队首的元素
        if(isEmpty()){
            return false;
        }
        //如果队列不为空，删除队首的元素，first+1，
        first = (first +1)% elements.length ; //必须保证first值到最大值时，能够再返回起点
        size = size-1;
        return true;

    }




    public boolean isEmpty() {
        //判断空，满足头标记与尾标记都相等，且无数值
        if( size ==0){
            return true;
        }
        return false;

    }
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        //如果队列不为空，返回队首元素
        return elements[first];
    }
    public boolean isFull() {
        if(first ==last && size>0){
            return true;
        }
        return false;
    }
}



public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());

    }
    public static void main3(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
       //这个类里面也实现了栈相关的方法
        //栈相关的方法是定义在Stack类当中，还是实现的接口中方法？
       //双端队列是一个接口，通过Linkedlist与ArrayDeque 两个类来实现











    }












    public static void main2(String[] args) {
        //任务 1. 用双链表实现队列
        //任务 2. 数组实现循环队列问题
   MyCircularQueue myCircularQueue = new MyCircularQueue(3);
   myCircularQueue.enQueue(1);
   myCircularQueue.enQueue(2);
   myCircularQueue.enQueue(3);
   myCircularQueue.enQueue(4);
   myCircularQueue.Rear();
   myCircularQueue.isFull();
   myCircularQueue.deQueue();
   myCircularQueue.enQueue(4);
   myCircularQueue.Rear();
    }
    public static void main1(String[] args) {
        LinkedList<Integer> stack =  new LinkedList<>();
        stack.push(5);
        stack.push(2);
        stack.pop();
        stack.pop();
        stack.pop();
    }
}
